package leetcode.f1t100;

/**
 * 给一个数组代表长度为1的挡板高度, 计算组成的最大矩形面积
 * https://leetcode.com/problems/largest-rectangle-in-histogram/
 *
 * @author lichx
 * @createTime 2024/1/30 14:02
 */
public class Q84_LargestRectangleInHistogram {

    public static void main(String[] args) {
        Q84_LargestRectangleInHistogram bean = new Q84_LargestRectangleInHistogram();
        int[] heights = {2};
        System.out.println(bean.largestRectangleArea(heights));
    }

    public int largestRectangleArea(int[] heights) {
        // 左边最近小于当前下标值的下标, 没有则-1
        int[] leftNearIndex = new int[heights.length];
        // 右边最近小于当前下标值的下标, 没有则数组长度
        int[] rightNearIndex = new int[heights.length];
        int point;
        leftNearIndex[0] = -1;

        for (int i = 1; i < heights.length; i++) {
            point = i - 1;
            while (point >= 0 && heights[point] >= heights[i]) {
                point = leftNearIndex[point];
            }
            leftNearIndex[i] = point;
        }
        rightNearIndex[heights.length - 1] = heights.length;
        for (int i = heights.length - 2; i >= 0; i--) {
            point = i + 1;
            while (point <= heights.length - 1 && heights[point] >= heights[i]) {
                point = rightNearIndex[point];
            }
            rightNearIndex[i] = point;
        }
        int area = 0;
        for (int i = 0; i < heights.length; i++) {
            // 面积等于当前位置的高度* (右边最近小于当前位置值下标-左边最近小于当前位置值下标 -1)
            area = Math.max(area, heights[i] * (rightNearIndex[i] - leftNearIndex[i] - 1));
        }
        return area;
    }

    public int largestRectangleArea_cache(int[] heights) {
        int[][] martix = new int[heights.length][heights.length];
        for (int i = 0; i < heights.length; i++) {
            martix[i][i] = heights[i];
        }
        for (int i = 0; i < heights.length; i++) {
            for (int j = i + 1; j < heights.length; j++) {
                martix[i][j] = Math.min(heights[j], martix[i][j - 1]);
            }
        }
        int temp = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                temp = Math.max(martix[i][j] * (j - i + 1), temp);
            }
        }
        return temp;
    }

    public int largestRectangleArea_for(int[] heights) {
        int temp = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    min = Math.min(min, heights[k]);
                }
                temp = Math.max(min * (j - i + 1), temp);
            }
        }
        return temp;
    }
}
